package algorithm.poj.p1000;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLDecoder;

/**
 * 分析：
 * 整数分拆
 * f(m,n) 是将m拆分成n个正整数的拆分方法个数，那么：
 * f(m,n) = simga f(m-n*k, n-t) (here, 1<= k <= m/n, 0 <= t <= n)
 * f(m,n) = 0, if (m < n)
 * f(m,m) = 1
 * 
 * g(m,n) 为所述问题的解，那么g(m,n) = sigma f(m,t) (here, t <= n)
 * 实现：
 * 
 * 经验：
 * 
 * 教训：
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P1664 {

	public static void main(String[] args) throws Exception {

		InputStream input = null;
		if (false) {
			input = System.in;
		} else {
			URL url = P1664.class.getResource("P1664.txt");
			File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
			input = new FileInputStream(file);
		}
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(input));

		String line = stdin.readLine();
		Integer t = Integer.valueOf(line);
		for (int i = 0; i < t; i ++) {
			line = stdin.readLine();
			String[] tmp = line.trim().split("\\s+");
			int M = Integer.valueOf(tmp[0]);
			int N = Integer.valueOf(tmp[1]);
			System.out.println(g(M, N));			
		}
	}
	
	private static long f(int m, int n) {
		
		if (m == 0 && n== 0) return 1;
		else if (m == n) return 1;
		else if (m < n || n == 0) return 0;
		else {
			long c = 0;
			for (int k = 1; k <= m/n; k ++) {
				for (int t = 1; t <= n; t ++) {
					c += f(m-n*k, n-t);
				}
			}
			return c;
		}
	}
	
	private static long g(int m, int n) {
		long c = 0;
		for (int t = 0; t <= n; t ++) {
			c += f(m,t);
		}
		return c;
	}
}